# coding: utf-8

import Queue

class FANode(object):
    
    cur_count = 0
    def __init__(self):
        FANode.cur_count += 1
        self.id = FANode.cur_count # for Debug
        self.next = {}
        self.type = 0
        self.is_end_state = False

def printf(cur_set):
    a = []
    for node in cur_set:
        a.append( [node.id, int(node.is_end_state)] )
    print a

class FA(object):
    
    def __init__(self):
        self.nfa_end   = FANode()
        self.nfa_start = FANode()
        self.dfa_start = FANode()

    def _get_move(self, pre_set, key):
        next_set = set()
        for node in pre_set:
            next_set.update( node.next[key] )
        queue = Queue.Queue()
        for node in next_set:
            queue.put(node)
        while not queue.empty():
            cur = queue.get()
            if "eps" not in cur.next.keys(): continue
            for node in cur.next["eps"]:
                if node not in next_set:
                    queue.put( node )
                    next_set.add( node )
        return next_set                    

    def nfa_to_dfa(self):
        self.dfa_start = FANode()
        cur   = self.dfa_start
        queue = Queue.Queue()
        queue.put( cur )
        temp_set = set()
        temp_set.add( self.nfa_start )
        start_set = self._get_move( temp_set, "eps" )
        get_state = { cur : start_set }
        get_state_node = { frozenset(start_set) : cur }     
        cur.is_end_state = True in [ node.is_end_state for node in start_set ]

        if cur.is_end_state == True:
            test_vis = { }
            for node in start_set:
                if node.type not in test_vis.keys():
                    test_vis[node.type] = 1;
                    
            for ty in test_vis.keys():
                next_node.type = ty

        count = 0

        while not queue.empty():
            cur = queue.get()
            cur_set = get_state[cur]
            to_vis_sets = { }
            
            for node in cur_set:
                for key in node.next.keys():
                    if key == "eps": 
                        # print 'whats the fuck'
                        continue
                    if key not in to_vis_sets.keys():
                        to_vis_sets[key] = set()
                    to_vis_sets[key].add(node)
            
            for key in to_vis_sets.keys():
                next_set = self._get_move( to_vis_sets[key], key )
                frozen_next = frozenset( next_set )
                if frozen_next not in get_state_node.keys():
                    next_node = FANode()
                    for node in next_set:
                        if node.is_end_state == True: 
                            next_node.is_end_state = True
                            # print node.type
                    # print '\n'
                    #next_node.is_end_state = True in [ node.is_end_state for node in next_set ]

                    if next_node.is_end_state: count += 1

                    if next_node.is_end_state == True:
                        test_vis = { }
                        for node in next_set:
                            if node.type not in test_vis.keys():
                                test_vis[node.type] = 1;
                        for ty in test_vis.keys():
                            next_node.type = ty

                    cur.next[key] = next_node
                    get_state[next_node] = next_set
                    queue.put( next_node )
                    get_state_node[frozen_next] = next_node
                else:
                    cur.next[key] = get_state_node[frozen_next]

        # print count